package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 无重叠区间
 */
public class Code03 {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 使用贪心算法解决问题.
        if (intervals.length <= 1) // 去掉不和规则的数组
            return 0;

        Arrays.sort(intervals, new Comparator<int[]>() { // 根据右节点的值对数组进行排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]); // 由小到大进行排序。 三种返回结果 大于返回1 小于返回-1 等于返回0
            }
        });

        int answer = 0;
        int[] nums;
        for (int r = intervals.length - 1; r >= 0; r--) { // 贪心的思路就是每次取最优解。所以每次的任务就是找到一个最短的左侧首区间
            nums = intervals[r];
            answer++;
            while (r-1 >= 0 && (intervals[r-1][0] > nums[0] || intervals[r-1][1] > nums[0])) { // 当我们没有完成这个任务的时候不能停下来。也就是当下一个区间在当前范围内，或者下一个区间和当前范围有冲突
                if (intervals[r-1][0] > nums[0]){
                    nums = intervals[r-1];
                }
                r--;
            }
        }

        return intervals.length - answer;
    }

    public int eraseOverlapIntervals2(int[][] intervals) {
        // 使用动态规划解决问题.
        if (intervals.length <= 1) // 去掉不和规则的数组
            return 0;

        Arrays.sort(intervals, new Comparator<int[]>() { // 根据右节点的值对数组进行排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]); // 由小到大进行排序。 三种返回结果 大于返回1 小于返回-1 等于返回0
            }
        });

        System.out.println("Arrays.deepToString(intervals) = " + Arrays.deepToString(intervals));

        int[] answer = new int[intervals.length];

        for (int r = intervals.length - 1; r >= 0; r--) {
            if (getN(r,intervals) != -1) // 如果intervals n 索引位置上有一个数组的左顶点恰好大于当前数组的右顶点.
                answer[r] = answer[getN(r,intervals)] + 1;
            else
                answer[r] = 1;
        }

        Arrays.sort(answer);
        return intervals.length - answer[answer.length-1];
    }

    public int getN(int r, int[][] intervals){
        int[] nums = intervals[r];

        for (int i = r+1; i < intervals.length; i++) {
            if (intervals[i][0] >= nums[1])
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Code03 code03 = new Code03();

        System.out.println("code03.eraseOverlapIntervals(new int[][]{{-52,31},{-73,-26},{82,97},{-65,-11},{-62,-49},{95,99},{58,95},{-31,49},{66,98},{-63,2},{30,47},{-40,-26}}) = " + code03.eraseOverlapIntervals2(new int[][]{{-62, -49}, {-73, -26}, {-40, -26}, {-65, -11}, {-63, 2}, {-52, 31}, {30, 47}, {-31, 49}, {58, 95}, {82, 97}, {66, 98}, {95, 99}}));
        System.out.println("code03.eraseOverlapIntervals(new int[][]{{1,2},{2,3},{3,4},{1,3}}) = " + code03.eraseOverlapIntervals2(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}));
        System.out.println("code03.eraseOverlapIntervals(new int[][]{{1,2},{1,2},{1,2}}) = " + code03.eraseOverlapIntervals2(new int[][]{{1, 2}, {1, 2}, {1, 2}}));
        System.out.println("code03.eraseOverlapIntervals(new int[][]{{1,2},{2,3}}) = " + code03.eraseOverlapIntervals2(new int[][]{{1, 2}, {2, 3}}));
    }
}
